package 链表;

import java.util.HashSet;
import java.util.Set;

public class No817链表组件 {

    /**
     * 给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。
     * 同时给定列表 G，该列表是上述链表中整型值的一个子集。
     * 返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。
     *
     * 示例 1：
     * 输入:
     * head: 0->1->2->3
     * G = [0, 1, 3]
     * 输出: 2
     * 解释:
     * 链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。
     * 示例 2：
     * 输入:
     * head: 0->1->2->3->4
     * G = [0, 3, 1, 4]
     * 输出: 2
     * 解释:
     * 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。
     */

    public static int numComponents(ListNode head, int[] G) {

        Set<Integer> set=new HashSet<>();
        for (int i : G) {
            set.add(i);
        }

        int count=0;
        boolean flag=false;

        while (head!=null){
            int val=head.val;

            if(set.contains(val)){
                //存在
                flag=true;
            }else{
                //不存在
                if(flag)//断开时重新集合+1,同时重新开始计数
                    count++;
                flag=false;
            }

            head=head.next;
        }

        if(flag)
            count++;

        return count;
    }

    public static void main(String[] args) {
        int[] arr=new int[]{0,1,2,3,4};
        ListNode listNode = ListNode.createListNode(arr);
        int[] g=new int[]{0,3,1,4};
        int result = numComponents(listNode, g);
        System.out.println(result);
    }

}
